class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        def judge(s, p):
            length = len(s)
            count = 0
            for i in range(length):
                count += (s[i] == p[i])
            return count == length - 1
        if endWord not in wordList:
            return 0
        search_set = {beginWord}
        now_search_set = [{beginWord}, {endWord}]
        step = 1
        while now_search_set[(step + 1) % 2]:
            print(now_search_set)
            if now_search_set[0] & now_search_set[1]:
                return step
            else:
                now_temp_set = now_search_set[(step + 1) % 2]
                new_search_set = set()
                for item in now_temp_set:
                    for word in wordList:
                        if word not in search_set:
                            if judge(item, word):
                                new_search_set.add(word)
                now_search_set[(step + 1) % 2] = new_search_set
                search_set.update(now_search_set[step % 2])
                step += 1

        return 0

data = Solution()
beginWord = "red"
endWord = "tax"
wordList = ["ted","tex","red","tax","tad","den","rex","pee"]
print(data.ladderLength(beginWord, endWord, wordList))
